package code1_100.code91_100;

import java.util.Stack;

/**
 * 相同的树：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 *
 */
public class _100equalTree {

    /**
     * 本质上是二叉树的遍历，此处使用先序遍历，多加几个判断即可
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 35.7 MB     * , 在所有 Java 提交中击败了     * 71.05%     * 的用户
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        TreeNode node1;
        TreeNode node2;
        if(p!=null){
            stack1.push(p);
            if(q!=null){
                stack2.push(q);
            }else {
                return false;
            }
        }else if(q!=null){
            return false;
        }

        while (stack1.size()!=0&&stack2.size()!=0){
            node1 = stack1.pop();
            node2 = stack2.pop();
            if(node1.val != node2.val){
                return false;
            }
            if(node1.left!=null||node2.left!=null){
                if (node1.left!=null&&node2.left!=null){
                    stack1.push(node1.left);
                    stack2.push(node2.left);
                }else {
                    return false;
                }
            }
            if(node1.right!=null||node2.right!=null){
                if (node1.right!=null&&node2.right!=null){
                    stack1.push(node1.right);
                    stack2.push(node2.right);
                }else {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        //先序结果：1245736
        //中序结果：4275136
        //后序结果：4752631
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node5.left = node7;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        root.right = node3;
        root.left = node2;

        //先序结果：1245736
        //中序结果：4275136
        //后序结果：4752631
        TreeNode aroot = new TreeNode(1);
        TreeNode anode2 = new TreeNode(2);
        TreeNode anode3 = new TreeNode(3);
        TreeNode anode4 = new TreeNode(4);
        TreeNode anode5 = new TreeNode(5);
        TreeNode anode6 = new TreeNode(6);
        TreeNode anode7 = new TreeNode(6);
        anode5.left = anode7;
        anode2.left = anode4;
        anode2.right = anode5;
        anode3.right = anode6;
        aroot.right = anode3;
        aroot.left = anode2;

        System.out.println(isSameTree(root,aroot));
    }

}
